import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class test {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>>res=new ArrayList<>();
        q(res,0,n,new ArrayList<String>());
        return res;
    }

    public void q(List<List<String>>res,int dep,int n,List<String> list){
        if(dep==n){
            List<String>temp= (List<String>) ((ArrayList<String>)list).clone();
            res.add(temp);
            return;
        }
        for(int col=0;col<n;col++){
            boolean flag=true;
            if(dep>0){
                for(int i=dep-1;i>=0;i--){
                    if((col-(dep-i)>=0)&&list.get(i).charAt(col-(dep-i))=='Q'){
                        flag=false;
                        break;
                    }
                    if((col+(dep-i)<n)&&list.get(i).charAt(col+(dep-i))=='Q'){
                        flag=false;
                        break;
                    }
                }
                for(String s:list){
                    if(s.charAt(col)=='Q'){
                        flag=false;
                        break;
                    }
                }
            }
            if(flag){
                List<String>temp= (List<String>) ((ArrayList<String>)list).clone();
                String str="";
                for(int i=0;i<n;i++){
                    if(i==col)
                        str+="Q";
                    else str+=".";
                }
                temp.add(str);
                q(res,dep+1,n,temp);
            }
        }
    }
    public boolean isValid(List<String>list,int dep,int col){
        if(dep==0)
            return true;
        for(int i=dep-1;i>=0;i--){
            if((col-(dep-i)>=0)&&list.get(i).charAt(col-(dep-i))=='Q')
                return false;
            if((col+(dep-i)<list.get(0).length())&&list.get(i).charAt(col+(dep-i))=='Q')
                return false;
        }
        for(String s:list){
            if(s.charAt(col)=='Q')
                return false;
        }
        return true;
    }
    public int removeElement(int[] nums, int val) {
        if(nums.length==0)
            return 0;
        int l=0,r=nums.length-1;
        for(;l<r;l++){
            if(nums[l]==val){
                while(nums[r]==val&&r>l)
                    r--;
                if(r>l){
                    int t=nums[r];
                    nums[r]=nums[l];
                    nums[l]=t;
                }
            }
        }
        if(l==r&&nums[l]!=val)
            l++;
        if(l>0&&nums[l-1]==val)
            l--;
        System.out.println(l);
        return l;

    }

        public static void main(String[] args) {
           test t=new test();
            List<List<String>> lists = t.solveNQueens(8);
            System.out.println(lists.size());

        }
}
class Solution1 {

    public int maxAreaOfIsland(int[][] grid) {
        int m=grid.length,n=grid[0].length;
        int max=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    int now=x(grid,i,j,m,n);
                    max= Math.max(now, max);
                }
            }
        }
        return max;
    }
    public int x(int[][]grid,int x,int y,int m,int n){
        int num=0;
        if(x<0||x>=m||y<0||y>=n||grid[x][y]==0)
            return 0;
        num++;
        grid[x][y]=0;
        num+=x(grid,x,y-1,m,n);
        num+=x(grid,x,y+1,m,n);
        num+=x(grid,x+1,y,m,n);
        num+=x(grid,x-1,y,m,n);
        return num;
    }

    public List<List<Integer>> subsets(int[] nums) {

        List<List<Integer>>res=new ArrayList();
        ArrayList<Integer>now=new ArrayList<Integer>();
        res.add(now);
        s(nums,res,now,0);
        return res;
    }
    public void s(int []nums,List<List<Integer>>res,List<Integer>now,int index){
//        ArrayList<Integer>temp= (ArrayList<Integer>) ((ArrayList<Integer>)now).clone();
       int i=0;
        for(;index<nums.length;index++,i++){
            if(i>0&&index>0&&nums[index]==nums[index-1])
                continue;
            ArrayList<Integer>temp= (ArrayList<Integer>) ((ArrayList<Integer>)now).clone();
            temp.add(nums[index]);
            res.add(temp);
            s(nums,res,temp,index+1);
        }
    }

}